package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/'>扁平化多级双向链表(Flatten a Multilevel Doubly Linked List)</a>
 * <p>你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。</p>
 * <p>给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。</p>
 * <p>返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * <a href='https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/'>查看示例</a>
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>节点数目不超过 1000</li>
 *         <li>1 <= Node.val <= 10^5</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/7 14:55
 */
public class LC430FlattenMultilevelDoublyLinkedList_M {
    static class Solution {
        public Node flatten(Node head) {
            Node dummy = new Node();
            dummy.next = head;
            while (head != null) {
                if (head.child != null) {
                    // 记录当前节点的下一个节点
                    Node nextNode = head.next;
                    // 扁平化子节点，并获取到 扁平化后链表的头
                    Node flattenListHead = flatten(head.child);
                    // 接上当前链表
                    head.next = flattenListHead;
                    flattenListHead.prev = head;
                    head.child = null;
                    // 找到扁平化后链表的尾
                    while (head.next != null) {
                        head = head.next;
                    }
                    // 如果当前节点的下一个节点不为null，改变指针指向
                    if (nextNode != null) {
                        head.next = nextNode;
                        nextNode.prev = head;
                    }
                }
                head = head.next;
            }
            return dummy.next;
        }
    }

    static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    public static void main(String[] args) {
        Node node1 = new Node();
        Node node2 = new Node();
        Node node3 = new Node();
        Node node4 = new Node();
        Node node5 = new Node();
        Node node6 = new Node();
        Node node7 = new Node();
        Node node8 = new Node();
        Node node9 = new Node();
        Node node10 = new Node();
        Node node11 = new Node();
        Node node12 = new Node();
        node1.val = 1;
        node2.val = 2;
        node3.val = 3;
        node4.val = 4;
        node5.val = 5;
        node6.val = 6;
        node7.val = 7;
        node8.val = 8;
        node9.val = 9;
        node10.val = 10;
        node11.val = 11;
        node12.val = 12;
        node1.next = node2;
        node2.prev = node1;
        node2.next = node3;
        node3.prev = node2;
        node3.next = node4;
        node3.child = node7;
        node4.prev = node3;
        node4.next = node5;
        node5.prev = node4;
        node5.next = node6;
        node6.prev = node5;
        node6.next = null;
        node7.next = node8;
        node8.prev = node7;
        node8.next = node9;
        node8.child = node11;
        node9.prev = node8;
        node9.next = node10;
        node10.prev = node9;
        node11.next = node12;
        node12.prev = node11;

        Solution solution = new Solution();
        Node flatten = solution.flatten(node1);
        while (flatten != null) {
            System.out.println(flatten.val);
            flatten = flatten.next;
        }
    }
}
